package pers.qianyu.month_202102.date_20210210;

import org.junit.*;

/**
 * 567. 字符串的排列
 * https://leetcode-cn.com/problems/permutation-in-string/
 * - 遍历一次的思路
 *
 * @author mizzle rain
 * @date 2021年2月10日22:43:37
 */
public class CheckInclusion2 {
    public boolean checkInclusion(String s1, String s2) {
        int[] need = new int[26];
        for (int i = 0; i < s1.length(); i++) need[s1.charAt(i) - 'a']++;
        int all = 0;
        for (int x : need) if (x > 0) all++;

        int left = 0, right = 0;
        int cnt = 0;
        int[] window = new int[26];
        while (right < s2.length()) {
            char c1 = s2.charAt(right);
            if (need[c1 - 'a'] > 0) {
                window[c1 - 'a']++;
                if (window[c1 - 'a'] == need[c1 - 'a']) cnt++;
            }
            right++;
            while (cnt == all) {
                if (right - left == s1.length()) return true;
                char c2 = s2.charAt(left);
                if (need[c2 - 'a'] > 0) {
                    window[c2 - 'a']--;
                    // 下面语句执行之后，循环就停止了
                    if (window[c2 - 'a'] < need[c2 - 'a']) cnt--;
                }
                left++;
            }
        }
        return false;
    }

    @Test
    public void test1() {
        boolean result = new CheckInclusion2().checkInclusion("hello", "ooolleoooleh");
        Assert.assertFalse(result);
    }
}